home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8649 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.2 KB  |  41 lines
  1. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  2. Path: undergrad.math.uwaterloo.ca!sckettle
  3. From: sckettle@undergrad.math.uwaterloo.ca (Steve Kettle)
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Sender: news@undergrad.math.uwaterloo.ca (news spool owner)
  6. Message-ID: <DnCnsA.J42@undergrad.math.uwaterloo.ca>
  7. Date: Sun, 25 Feb 1996 21:02:33 GMT
  8. References: <4fr8be$ass@news.iconn.net> <DMruKv.CCp@research.att.com>
  9. Nntp-Posting-Host: noether.math.uwaterloo.ca
  10. Organization: University of Waterloo
  11.  
  12. The way to do this problem in a brute force way is:
  13.  
  14. - prime factorize n - not to hard you already have n factors
  15.   so you get something like 2^a * 3^b * 5^c ...
  16.  
  17. - now cast away the fives by pairing with twos
  18.   so you get something like 2^(a-c) * 3^b * 7^d
  19.  
  20. - now just multiply all the terms together only remembering 
  21. the last digit each time ( just take it mod 10 after is 
  22. multiply ).
  23.  
  24.  
  25.  
  26. eg.  LASTNONZERODIGITOF(6!)
  27.     = LASTNONZERODIGITOF(2^4 * 3^2 * 5)
  28.     = LASTNONZERODIGITOF(2^3 * 3^2)
  29.     = No Problem can't get messed up by 10's!
  30.  
  31.  
  32. - I bet though there is a MUCH faster way of doing this.
  33.  
  34. - Question for you - what is the running time of the above 
  35.   algorithm? 
  36.  
  37.  
  38.  
  39.  
  40. -- 
  41.